{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Array into Consecutive Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isPossible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割数组为连续子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个按 <strong>非递减顺序</strong> 排列的整数数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>请你判断是否能在将 <code>nums</code> 分割成 <strong>一个或多个子序列</strong> 的同时满足下述 <strong>两个</strong> 条件：</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<ul>\n",
    "\t<li>每个子序列都是一个 <strong>连续递增序列</strong>（即，每个整数 <strong>恰好</strong> 比前一个整数大 <strong>1</strong> ）。</li>\n",
    "\t<li>所有子序列的长度 <strong>至少</strong> 为 <code>3</code><strong> </strong>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果可以分割 <code>nums</code> 并满足上述条件，则返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,3,4,5]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>nums 可以分割成以下子序列：\n",
    "[<em><strong>1</strong></em>,<em><strong>2</strong></em>,<em><strong>3</strong></em>,3,4,5] --&gt; 1, 2, 3\n",
    "[1,2,3,<em><strong>3</strong></em>,<em><strong>4</strong></em>,<em><strong>5</strong></em>] --&gt; 3, 4, 5\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,3,4,4,5,5]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>nums 可以分割成以下子序列：\n",
    "[<em><strong>1</strong></em>,<em><strong>2</strong></em>,<em><strong>3</strong></em>,3,<em><strong>4</strong></em>,4,<em><strong>5</strong></em>,5] --&gt; 1, 2, 3, 4, 5\n",
    "[1,2,3,<em><strong>3</strong></em>,4,<em><strong>4</strong></em>,5,<em><strong>5</strong></em>] --&gt; 3, 4, 5\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4,4,5]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>无法将 nums 分割成长度至少为 3 的连续递增子序列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>nums</code> 按非递减顺序排列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-array-into-consecutive-subsequences](https://leetcode.cn/problems/split-array-into-consecutive-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-array-into-consecutive-subsequences](https://leetcode.cn/problems/split-array-into-consecutive-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,3,4,5]', '[1,2,3,3,4,4,5,5]', '[1,2,3,4,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        counts = {}\n",
    "        for num in nums:\n",
    "            counts[num] = counts.get(num, 0) + 1\n",
    "\n",
    "        arr_count = {}\n",
    "        for num in nums:\n",
    "            if counts[num] == 0:\n",
    "                continue\n",
    "            if arr_count.get(num-1, 0) == 0:\n",
    "                if counts.get(num+1, 0) == 0 or counts.get(num+2, 0) == 0:\n",
    "                    return False\n",
    "                counts[num+1] -= 1\n",
    "                counts[num+2] -= 1\n",
    "                arr_count[num+2] = arr_count.get(num+2, 0) + 1\n",
    "            else:\n",
    "                arr_count[num-1] -= 1\n",
    "                arr_count[num] = arr_count.get(num, 0) + 1\n",
    "            counts[num] -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        d=defaultdict(int)\n",
    "        c=Counter(nums)\n",
    "        for v in nums:\n",
    "            if c[v]==0:continue\n",
    "            if d[v]>0:\n",
    "                d[v+1]+=1\n",
    "                d[v]-=1\n",
    "                c[v]-=1\n",
    "            else:\n",
    "                if c[v+1]>0 and c[v+2]>0:\n",
    "                    d[v+3]+=1\n",
    "                    c[v]-=1\n",
    "                    c[v+1]-=1\n",
    "                    c[v+2]-=1\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        d = defaultdict(list)\n",
    "        for i in nums:\n",
    "            if i - 1 in d and d[i-1]:\n",
    "                heapq.heapify(d[i-1])\n",
    "                d[i].append(heapq.heappop(d[i-1])+1)\n",
    "            else:\n",
    "                d[i].append(1)\n",
    "        for i in d:\n",
    "            for j in d[i]:\n",
    "                if j < 3:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i - 1 in dic:\n",
    "                lis = dic[i - 1]\n",
    "                m = min(lis)\n",
    "                index = lis.index(m)\n",
    "                if i in dic:\n",
    "                    dic[i].append(lis[index] + 1)\n",
    "                else:\n",
    "\n",
    "                    dic[i] = [lis[index] + 1]\n",
    "                lis.remove(lis[index])\n",
    "                if len(lis) == 0:\n",
    "                    dic.pop(i - 1)\n",
    "                else:\n",
    "                    dic[i - 1] = lis\n",
    "            else:\n",
    "                if i in dic:\n",
    "                    dic[i].append(1)\n",
    "                else:\n",
    "                    dic[i] = [1]\n",
    "        res = True\n",
    "        for value in dic.values():\n",
    "            for i in value:\n",
    "                if i<3:\n",
    "                    res=False\n",
    "                    break\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        # freq 哈希表帮助一个元素判断自己是否能够作为开头，need 哈希表帮助一个元素判断自己是否可以被接到其他序列后面。\n",
    "        freq,need = defaultdict(int),defaultdict(int) #使用defaultdict自动有默认值\n",
    "        for v in nums:\n",
    "            freq[v] = freq[v]+1\n",
    "        # 应该优先判断自己是否能够接到其他序列后面，如果不行，再判断是否可以作为新的子序列开头。\n",
    "        for v in nums:\n",
    "            if freq[v]==0:\n",
    "                continue\n",
    "            elif v in need and need[v]>0:\n",
    "                freq[v]-=1\n",
    "                need[v]-=1\n",
    "                need[v+1]+=1\n",
    "            elif freq[v] > 0 and freq.get(v + 1, 0) > 0 and freq.get(v + 2, 0) > 0:\n",
    "                # 将 v 作为开头，新建一个长度为 3 的子序列 [v,v+1,v+2]\n",
    "                freq[v] -= 1\n",
    "                freq[v + 1] -= 1\n",
    "                freq[v + 2] -= 1\n",
    "                need[v + 3] += 1\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums) -> bool:\n",
    "        from collections import Counter\n",
    "        n = len(nums)\n",
    "        dic = Counter(nums)\n",
    "        dic1 = Counter()\n",
    "        for i in range(n):\n",
    "            if dic1[nums[i]] > 0:\n",
    "                dic1[nums[i]] -= 1\n",
    "                dic1[nums[i] + 1] += 1\n",
    "            else:\n",
    "                if not dic[nums[i] + 1] or not dic[nums[i] + 2]:\n",
    "                    return False\n",
    "                dic[nums[i] + 1] -= 1\n",
    "                dic[nums[i] + 2] -= 1\n",
    "                dic1[nums[i] + 1] += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        freq, need = {}, {}\n",
    "        for v in nums:\n",
    "            freq[v] = freq.get(v, 0) + 1\n",
    "        for v in nums:\n",
    "            if freq[v] == 0:\n",
    "                continue\n",
    "            if v in need and need[v] > 0:\n",
    "                freq[v] -= 1\n",
    "                need[v] -= 1\n",
    "                need[v+1] = need.get(v + 1, 0) + 1\n",
    "            elif freq[v] > 0 and freq.get(v+1,0) > 0 and freq.get(v+2, 0) > 0:\n",
    "                freq[v] -= 1\n",
    "                freq[v+1] -= 1\n",
    "                freq[v+2] -= 1\n",
    "                need[v+3] = need.get(v+3, 0) + 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        countMap = collections.Counter(nums)\n",
    "        endMap = collections.Counter()\n",
    "\n",
    "        for x in nums:\n",
    "            if (count := countMap[x]) > 0:\n",
    "                if (prevEndCount := endMap.get(x - 1, 0)) > 0:\n",
    "                    countMap[x] -= 1\n",
    "                    endMap[x - 1] = prevEndCount - 1\n",
    "                    endMap[x] += 1\n",
    "                else:\n",
    "                    if (count1 := countMap.get(x + 1, 0)) > 0 and (count2 := countMap.get(x + 2, 0)) > 0:\n",
    "                        countMap[x] -= 1\n",
    "                        countMap[x + 1] -= 1\n",
    "                        countMap[x + 2] -= 1\n",
    "                        endMap[x + 2] += 1\n",
    "                    else:\n",
    "                        return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        fre=Counter(nums)\n",
    "        end=defaultdict(int)\n",
    "        for num in nums:\n",
    "            if fre[num]==0:\n",
    "                continue\n",
    "            fre[num]-=1\n",
    "\n",
    "            if end[num-1]>0:\n",
    "                end[num-1]-=1\n",
    "                end[num]+=1\n",
    "            elif fre[num+1]>0 and fre[num+2]>0:\n",
    "                fre[num+1]-=1\n",
    "                fre[num+2]-=1\n",
    "                end[num+2]+=1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        countMap = collections.Counter(nums)\n",
    "        endMap = collections.Counter()\n",
    "\n",
    "        for x in nums:\n",
    "            if (count := countMap[x]) > 0:\n",
    "                if (prevEndCount := endMap.get(x - 1, 0)) > 0:\n",
    "                    countMap[x] -= 1\n",
    "                    endMap[x - 1] = prevEndCount - 1\n",
    "                    endMap[x] += 1\n",
    "                else:\n",
    "                    if (count1 := countMap.get(x + 1, 0)) > 0 and (count2 := countMap.get(x + 2, 0)) > 0:\n",
    "                        countMap[x] -= 1\n",
    "                        countMap[x + 1] -= 1\n",
    "                        countMap[x + 2] -= 1\n",
    "                        endMap[x + 2] += 1\n",
    "                    else:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        # 使用字典统计 nums 中元素的频率\n",
    "        freq, need = {}, {}\n",
    "        for v in nums:\n",
    "            freq[v] = freq.get(v, 0) + 1\n",
    "\n",
    "        for v in nums:\n",
    "            if freq[v] == 0:\n",
    "                # 已经被用到其他子序列中\n",
    "                continue\n",
    "            if v in need and need[v] > 0:\n",
    "                # v 可以接到之前的某个序列后面\n",
    "                freq[v] -= 1\n",
    "                need[v] -= 1\n",
    "                need[v + 1] = need.get(v + 1, 0) + 1\n",
    "            elif freq[v] > 0 and freq.get(v + 1, 0) > 0 and freq.get(v + 2, 0) > 0:\n",
    "                # 将 v 作为开头，新建一个长度为 3 的子序列 [v,v+1,v+2]\n",
    "                freq[v] -= 1\n",
    "                freq[v + 1] -= 1\n",
    "                freq[v + 2] -= 1\n",
    "                need[v + 3] = need.get(v + 3, 0) + 1\n",
    "            else:\n",
    "                # 两种情况都不符合，则无法分配\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        one, two, three = {}, {}, {}    # one[8]表示8的频次，two[8]表示[7,8]的频次，three[8]表示[...,6,7,8]的频次\n",
    "        for v in nums:\n",
    "            if v-1 in one:\n",
    "                one[v-1] -= 1\n",
    "                if not one[v-1]:\n",
    "                    del one[v-1]\n",
    "                if v not in two:\n",
    "                    two[v] = 1\n",
    "                else:\n",
    "                    two[v] += 1\n",
    "            elif v-1 in two:\n",
    "                two[v-1] -= 1\n",
    "                if not two[v-1]:\n",
    "                    del two[v-1]\n",
    "                if v not in three:\n",
    "                    three[v] = 1\n",
    "                else:\n",
    "                    three[v] += 1\n",
    "            elif v-1 in three:\n",
    "                three[v-1] -= 1\n",
    "                if not three[v-1]:\n",
    "                    del three[v-1]\n",
    "                if v not in three:\n",
    "                    three[v] = 1\n",
    "                else:\n",
    "                    three[v] += 1\n",
    "            else:\n",
    "                if v not in one:\n",
    "                    one[v] = 1\n",
    "                else:\n",
    "                    one[v] += 1\n",
    "        return not one and not two\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "# 贪心法\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        freq = defaultdict(int)\n",
    "        need = defaultdict(int)\n",
    "        \n",
    "        for v in nums:\n",
    "            freq[v] += 1\n",
    "        for v in nums:\n",
    "            if freq[v] == 0: # 已经被用了\n",
    "                continue\n",
    "            if need[v] > 0: # 判断是否能接到其他子队列后面\n",
    "                freq[v] -= 1\n",
    "                need[v] -= 1\n",
    "                need[v + 1] += 1\n",
    "            elif freq[v] > 0 and freq[v + 1] > 0 and freq[v + 2] > 0:\n",
    "                freq[v] -= 1\n",
    "                freq[v + 1] -= 1\n",
    "                freq[v + 2] -= 1\n",
    "                need[v + 3] += 1\n",
    "                \n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        num_count = {}\n",
    "        end_count = {}\n",
    "        for num in nums:\n",
    "            if num not in num_count:\n",
    "                num_count[num] = 0\n",
    "            num_count[num] += 1\n",
    "\n",
    "        for num in nums:\n",
    "            if num_count[num] == 0:\n",
    "                continue\n",
    "            elif end_count.get(num-1, 0) > 0:\n",
    "                end_count[num-1] -= 1\n",
    "                if num in end_count:\n",
    "                    end_count[num] += 1\n",
    "                else:\n",
    "                    end_count[num] = 1\n",
    "                num_count[num] -= 1\n",
    "            elif num_count.get(num+1, 0) > 0 and num_count.get(num+2, 0) > 0:\n",
    "                num_count[num] -= 1\n",
    "                num_count[num+1] -= 1\n",
    "                num_count[num+2] -= 1\n",
    "                if num+2 in end_count:\n",
    "                    end_count[num+2] += 1\n",
    "                else:\n",
    "                    end_count[num+2] = 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        ml = collections.defaultdict(list)\n",
    "        for i in nums:\n",
    "            if ml.__contains__(i - 1):\n",
    "                cur = ml.get(i - 1)\n",
    "                if len(cur) > 0:\n",
    "                    heapq.heappush(ml[i], heapq.heappop(cur) + 1)\n",
    "                else:\n",
    "                    heapq.heappush(ml[i], 1)\n",
    "            else:\n",
    "                heapq.heappush(ml[i], 1)\n",
    "        return all(k > 2 for k in sum(ml.values(), []))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        mp = collections.defaultdict(list)\n",
    "        for x in nums:\n",
    "            if queue := mp.get(x - 1):\n",
    "                prevLength = heapq.heappop(queue)\n",
    "                heapq.heappush(mp[x], prevLength + 1)\n",
    "            else:\n",
    "                heapq.heappush(mp[x], 1)\n",
    "        \n",
    "        return not any(queue and queue[0] < 3 for queue in mp.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "\n",
    "        end_length_dict = {}\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            if x-1 in end_length_dict.keys():\n",
    "                min_length = min(end_length_dict[x-1])\n",
    "                if x in end_length_dict.keys():\n",
    "                    end_length_dict[x].append(min_length+1)\n",
    "                else:\n",
    "                    end_length_dict[x] = [min_length+1]\n",
    "                end_length_dict[x-1].remove(min_length)\n",
    "                if len(end_length_dict[x-1]) == 0:\n",
    "                    end_length_dict.pop(x-1)\n",
    "            else:\n",
    "                if x not in end_length_dict.keys():\n",
    "                    end_length_dict[x] = [1]\n",
    "                else:\n",
    "                    end_length_dict[x].append(1)\n",
    "            # print(end_length_dict)\n",
    "        \n",
    "        for key, val in end_length_dict.items():\n",
    "            for i, length in enumerate(val):\n",
    "                if length < 3:\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3: return False\n",
    "        arr = [[nums[0], 1]]\n",
    "        size, cnt = 1, 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > arr[-1][0] + 1:\n",
    "                arr.append([nums[i], 1])\n",
    "                size += 1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                index = bisect.bisect_left(arr, [nums[i] - 1])\n",
    "                if arr[index][0] == nums[i] - 1:\n",
    "                    arr[index][0] = nums[i]\n",
    "                    if arr[index][1] == 2: cnt -= 1\n",
    "                    arr[index][1] += 1\n",
    "                    tmp = arr.pop(index)\n",
    "                    index = bisect.bisect_left(arr, tmp)\n",
    "                    arr.insert(index, tmp)\n",
    "                else:\n",
    "                    arr.insert(index, [nums[i], 1])\n",
    "                    cnt += 1\n",
    "                    size += 1\n",
    "        return cnt == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        ln1, ln2, red = Counter(), Counter(), Counter()\n",
    "        for i in nums:\n",
    "            if ln2[i - 1]:\n",
    "                ln2[i - 1] -= 1\n",
    "                red[i] += 1\n",
    "            elif ln1[i - 1]:\n",
    "                ln1[i - 1] -= 1\n",
    "                ln2[i] += 1\n",
    "            elif red[i - 1]:\n",
    "                red[i - 1] -= 1\n",
    "                red[i] += 1\n",
    "            else:\n",
    "                ln1[i] += 1\n",
    "        s = 0\n",
    "        s += sum(ln1.values()) + sum(ln2.values())\n",
    "        return s == 0\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def isPossible(self, nums: List[int]) -> bool:\r\n",
    "        memo={}\r\n",
    "        for n in nums:\r\n",
    "            if n-1 in memo and len(memo[n-1]):\r\n",
    "                segs=memo[n-1]\r\n",
    "                seg_len=heapq.heappop(segs)\r\n",
    "                next_segs=memo.setdefault(n,[])\r\n",
    "                heapq.heappush(next_segs,seg_len+1)\r\n",
    "            else:\r\n",
    "                segs=memo.setdefault(n,[])\r\n",
    "                heapq.heappush(segs,1)\r\n",
    "        for segs_len in memo.values():\r\n",
    "            if len(segs_len) and segs_len[0]<3:\r\n",
    "                return False\r\n",
    "        return True\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        freq = {}\n",
    "        end_dict = {}\n",
    "\n",
    "        for n in nums:\n",
    "            freq[n] = freq.get(n, 0) + 1\n",
    "        \n",
    "        for n in nums:\n",
    "            if freq[n] == 0: continue\n",
    "\n",
    "            freq[n] -= 1\n",
    "            if n - 1 in end_dict and end_dict[n - 1]:\n",
    "                end_dict[n - 1] -= 1\n",
    "                end_dict[n] = end_dict.get(n, 0) + 1\n",
    "            elif n + 1 in freq and freq[n+1] and n+2 in freq and freq[n + 2]:\n",
    "                freq[n+1] -= 1\n",
    "                freq[n + 2] -= 1\n",
    "                end_dict[n + 2] = end_dict.get(n+2, 0) + 1\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        mp = collections.defaultdict(list)\n",
    "        for x in nums:\n",
    "            if queue := mp.get(x - 1):\n",
    "                prevLength = heapq.heappop(queue)\n",
    "                heapq.heappush(mp[x], prevLength + 1)\n",
    "            else:\n",
    "                heapq.heappush(mp[x], 1)\n",
    "        return not any(queue and queue[0] < 3 for queue in mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n<3: return False\n",
    "        d = collections.defaultdict(list)\n",
    "        # d[10] = [3,4,5]:以9为结尾的序列的有三个。分别为3 4 5 \n",
    "        #由于子序列连续递增，结尾和长度可以唯一确定序列\n",
    "        #本题的关键：贪心，如果多个序列需要该数字，给最短的序列就好\n",
    "        #因为其实给每一个序列都是一样的，而最短的序列最不可能满足长度大于等于3的要求\n",
    "        #如果都满足的话，那其实给每个序列都是一样的\n",
    "        #所以维护最小堆\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                l = heapq.heappop(d[num])\n",
    "                if not d[num]: del d[num]\n",
    "                heapq.heappush(d[num+1],l+1)\n",
    "            else:\n",
    "                heapq.heappush(d[num+1],1)\n",
    "        for ls in d.values():\n",
    "            for l in ls:\n",
    "                if l<3: return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        mp = collections.defaultdict(list)\n",
    "\n",
    "        for n in nums:\n",
    "            if n - 1 in mp:\n",
    "                length = heapq.heappop(mp[n - 1])\n",
    "                if not mp[n - 1]:\n",
    "                    del mp[n - 1]\n",
    "                \n",
    "                newlen = length + 1\n",
    "                heapq.heappush(mp[n], newlen)\n",
    "            else:\n",
    "                heapq.heappush(mp[n], 1)\n",
    "\n",
    "        for key in mp:\n",
    "            if mp[key][0] < 3:\n",
    "                return False\n",
    "        return True    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        freq = {}\n",
    "        need = {}\n",
    "        for n in nums:\n",
    "            freq[n] = freq.get(n, 0) + 1\n",
    "        \n",
    "        # print('freq:', freq)\n",
    "\n",
    "        for n in nums:\n",
    "            if freq.get(n, 0) == 0:\n",
    "                continue\n",
    "            elif need.get(n, 0) > 0:\n",
    "                freq[n] = freq[n] - 1\n",
    "                need[n] = need[n] - 1\n",
    "                need[n+1] = need.get(n+1, 0) + 1\n",
    "            elif freq.get(n, 0) > 0 and freq.get(n+1, 0) > 0 and freq.get(n+2, 0) > 0:\n",
    "                freq[n] = freq[n]-1\n",
    "                freq[n+1] = freq[n+1]-1\n",
    "                freq[n+2] = freq[n+2]-1\n",
    "                need[n+3] = need.get(n+3, 0) + 1\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        num_count = {}\n",
    "        end_count = {}\n",
    "        for num in nums:\n",
    "            if num not in num_count:\n",
    "                num_count[num] = 0\n",
    "            num_count[num] += 1\n",
    "\n",
    "        for num in nums:\n",
    "            if num_count[num] == 0:\n",
    "                continue\n",
    "            elif end_count.get(num-1, 0) > 0:\n",
    "                end_count[num-1] -= 1\n",
    "                if num in end_count:\n",
    "                    end_count[num] += 1\n",
    "                else:\n",
    "                    end_count[num] = 1\n",
    "                num_count[num] -= 1\n",
    "            elif num_count.get(num+1, 0) > 0 and num_count.get(num+2, 0) > 0:\n",
    "                num_count[num] -= 1\n",
    "                num_count[num+1] -= 1\n",
    "                num_count[num+2] -= 1\n",
    "                if num+2 in end_count:\n",
    "                    end_count[num+2] += 1\n",
    "                else:\n",
    "                    end_count[num+2] = 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        d = defaultdict(lambda :[]) #key=结尾数字，value=长度堆\n",
    "        for x in nums:\n",
    "            if len(d.get(x-1,[])) == 0:\n",
    "                heapq.heappush(d[x],1)\n",
    "            else:\n",
    "                len_ = heappop(d[x-1])\n",
    "                heapq.heappush(d[x],len_+1)\n",
    "        return not any(q and q[0]<3 for q in d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        cnt=defaultdict(list)\n",
    "        for i,num in enumerate(nums):\n",
    "            if len(cnt[num-1])==0:\n",
    "                heappush(cnt[num],1)\n",
    "            else:\n",
    "                length=heappop(cnt[num-1])\n",
    "                heappush(cnt[num],length+1)\n",
    "        ans=True\n",
    "        for key,value in cnt.items():\n",
    "            for num in value:\n",
    "                if num<3:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        # freq 哈希表帮助一个元素判断自己是否能够作为开头，need 哈希表帮助一个元素判断自己是否可以被接到其他序列后面。\n",
    "        freq,need = defaultdict(int),defaultdict(int) #使用defaultdict自动有默认值\n",
    "        for v in nums:\n",
    "            freq[v] = freq[v]+1\n",
    "        # 应该优先判断自己是否能够接到其他序列后面，如果不行，再判断是否可以作为新的子序列开头。\n",
    "        for v in nums:\n",
    "            if freq[v]==0:\n",
    "                continue\n",
    "            elif v in need and need[v]>0:\n",
    "                freq[v]-=1\n",
    "                need[v]-=1\n",
    "                need[v+1]+=1\n",
    "            elif freq[v] > 0 and freq.get(v + 1, 0) > 0 and freq.get(v + 2, 0) > 0:\n",
    "                # 将 v 作为开头，新建一个长度为 3 的子序列 [v,v+1,v+2]\n",
    "                freq[v] -= 1\n",
    "                freq[v + 1] -= 1\n",
    "                freq[v + 2] -= 1\n",
    "                need[v + 3] += 1\n",
    "            else:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        mp = collections.defaultdict(list)\n",
    "        for x in nums:\n",
    "            if queue := mp.get(x - 1):\n",
    "                prevLength = heapq.heappop(queue)\n",
    "                heapq.heappush(mp[x], prevLength + 1)\n",
    "            else:\n",
    "                heapq.heappush(mp[x], 1)\n",
    "        \n",
    "        return not any(queue and queue[0] < 3 for queue in mp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        need = {}\n",
    "        count = {}\n",
    "        for n in nums:\n",
    "            count[n] = count.get(n,0) + 1\n",
    "        for n in nums:\n",
    "            # print(n,need)\n",
    "            if count.get(n,0) == 0:\n",
    "                continue\n",
    "            if need.get(n,0) > 0:\n",
    "                count[n] -= 1\n",
    "                need[n] -= 1\n",
    "                need[n+1] = need.get(n+1,0) + 1\n",
    "            elif count.get(n+1,0) > 0 and count.get(n+2,0) > 0:\n",
    "                count[n] -= 1\n",
    "                count[n+1] -= 1\n",
    "                count[n+2] -= 1\n",
    "                need[n+3] = need.get(n+3,0)+1\n",
    "            else:\n",
    "                # print(n)\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        mp = collections.defaultdict(list)\n",
    "        for x in nums:\n",
    "            if queue := mp.get(x - 1):\n",
    "                prevLength = heapq.heappop(queue)\n",
    "                heapq.heappush(mp[x], prevLength + 1)\n",
    "            else:\n",
    "                heapq.heappush(mp[x], 1)\n",
    "        \n",
    "        return not any(queue and queue[0] < 3 for queue in mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        for num in nums:\n",
    "            if len(d[num - 1]) > 0:\n",
    "                l = heappop(d[num - 1])\n",
    "                heappush(d[num], l + 1)\n",
    "            else:\n",
    "                heappush(d[num], 1)\n",
    "        return min(reduce(lambda x, y: x + y, d.values())) > 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n<3: return False\n",
    "        d = collections.defaultdict(list)\n",
    "        # d[10] = [3,4,5]:以9为结尾的序列的有三个。长度分别为3 4 5 \n",
    "        #由于子序列连续递增，结尾和长度可以唯一确定序列\n",
    "        #本题的关键：贪心，如果多个序列需要该数字，给最短的序列就好\n",
    "        #因为其实给每一个序列都是一样的，而最短的序列最不可能满足长度大于等于3的要求\n",
    "        #如果都满足的话，那其实给每个序列都是一样的\n",
    "        #所以维护最小堆\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                l = heapq.heappop(d[num])\n",
    "                if not d[num]: del d[num]\n",
    "                heapq.heappush(d[num+1],l+1)\n",
    "            else:\n",
    "                heapq.heappush(d[num+1],1)\n",
    "        for ls in d.values():\n",
    "            for l in ls:\n",
    "                if l<3: return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isPossible(self, nums: List[int]) -> bool:\r\n",
    "        dic = {}\r\n",
    "        for v in nums:\r\n",
    "            if v in dic:\r\n",
    "                dic[v] += 1\r\n",
    "            else:\r\n",
    "                dic[v] = 1\r\n",
    "        for key in dic:\r\n",
    "            a, b, c, d = 0, 0, 0, 0\r\n",
    "            if key - 2 in dic:\r\n",
    "                a = dic[key - 2]\r\n",
    "            if key - 1 in dic:\r\n",
    "                b = dic[key - 1]\r\n",
    "            if key + 1 in dic:\r\n",
    "                c = dic[key + 1]\r\n",
    "            if key + 2 in dic:\r\n",
    "                d = dic[key + 2]    \r\n",
    "            if min(b + d, a + c, b + c) < dic[key]:\r\n",
    "                return(False)\r\n",
    "        return(True)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        d = {} #key=结尾数字，value=长度堆\n",
    "        for x in nums:\n",
    "            if len(d.get(x-1,[])) == 0:\n",
    "                d[x] = d.get(x,[])\n",
    "                heapq.heappush(d[x],1)\n",
    "            else:\n",
    "                len_ = heappop(d[x-1])\n",
    "                d[x] = d.get(x,[])\n",
    "                heapq.heappush(d[x],len_+1)\n",
    "        for k,v in d.items():\n",
    "            if len(v) and heapq.heappop(v)<3:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "   def isPossible(self, nums: List[int]) -> bool:\n",
    "        mp = collections.defaultdict(list)\n",
    "        for x in nums:\n",
    "            queue = mp.get(x - 1)\n",
    "            if queue:\n",
    "                prevLength = heapq.heappop(queue)\n",
    "                heapq.heappush(mp[x], prevLength + 1)\n",
    "            else:\n",
    "                heapq.heappush(mp[x], 1)\n",
    "        \n",
    "        return not any(queue and queue[0] < 3 for queue in mp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        mp = collections.defaultdict(list)\n",
    "        for x in nums:\n",
    "            queue = mp.get(x-1)\n",
    "            if queue and len(queue)>0:\n",
    "                pre_length = heapq.heappop(queue)\n",
    "                heapq.heappush(mp[x], pre_length+1)\n",
    "            else:\n",
    "                heapq.heappush(mp[x], 1)\n",
    "        return not any(queue and queue[0]<3 for queue in mp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        need = Counter()\n",
    "        have = Counter(nums)\n",
    "        for num in nums:\n",
    "            if have[num] == 0:\n",
    "                continue\n",
    "            if need[num] > 0:\n",
    "                have[num] -= 1\n",
    "                need[num] -= 1\n",
    "                need[num + 1] += 1\n",
    "            elif have[num + 1] > 0 and have[num + 2] > 0:\n",
    "                have[num] -= 1\n",
    "                have[num + 1] -= 1\n",
    "                have[num + 2] -= 1\n",
    "                need[num + 3] += 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        freq = {}\n",
    "        need = {}\n",
    "        # 初始化freq\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in freq:\n",
    "                freq[nums[i]] = 1\n",
    "            else:\n",
    "                freq[nums[i]] += 1\n",
    "        for v in nums:\n",
    "            if freq[v] == 0:\n",
    "                continue\n",
    "            if v in need and need[v] > 0:\n",
    "                freq[v] -= 1\n",
    "                need[v] -= 1\n",
    "                if v+1 not in need:\n",
    "                    need[v+1] = 1\n",
    "                else:\n",
    "                    need[v+1] += 1\n",
    "            elif freq[v] > 0 and freq.get(v+1, 0) > 0 and freq.get(v+2, 0) > 0:\n",
    "                freq[v] -= 1\n",
    "                freq[v+1] -= 1\n",
    "                freq[v+2] -= 1\n",
    "                need[v+3] = need.get(v+3, 0) + 1\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res=[]\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n==v[-1]+1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0,[n])\n",
    "        return all([len(u)>=3 for u in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        #贪心+堆+哈希表\n",
    "        #思路有点难想\n",
    "        x=defaultdict(list)\n",
    "        #哈希表里key存子序列结尾元素,value存子序列长度的最小堆,因为每次贪心地把当前元素分配到长度最小的连续子序列上,这样尽可能保证所有子序列的长度 至少 为 3 。\n",
    "        for v in nums:\n",
    "            if cur:=x.get(v-1):\n",
    "                lent=heapq.heappop(cur)\n",
    "                heapq.heappush(x[v],lent+1)\n",
    "            else:\n",
    "                heapq.heappush(x[v],1)\n",
    "        return all(min(x[a])>=3 for a in x if x[a])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        #贪心+堆+哈希表\n",
    "        #思路有点难想\n",
    "        x=defaultdict(list)\n",
    "        #哈希表里key存子序列结尾元素,value存子序列长度的最小堆,因为每次贪心地把当前元素分配到长度最小的连续子序列上,这样尽可能保证所有子序列的长度 至少 为 3 。\n",
    "        for v in nums:\n",
    "            #一定要这样写,否则v-1 in x 是会报错的\n",
    "            if cur:=x.get(v-1):\n",
    "                lent=heapq.heappop(cur)\n",
    "                heapq.heappush(x[v],lent+1)\n",
    "            else:\n",
    "                heapq.heappush(x[v],1)\n",
    "        return all(min(x[a])>=3 for a in x if x[a])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from collections import defaultdict \n",
    "class Solution:\n",
    "  def isPossible(self, nums) :\n",
    "    d = defaultdict(list)\n",
    "    for item in nums:\n",
    "        if d[item - 1]:\n",
    "            q = d[item- 1]\n",
    "            length = heappop(q)\n",
    "            heappush(d[item], length + 1)\n",
    "        else:\n",
    "            heappush(d[item], 1)\n",
    "    for k in d:\n",
    "        if d[k] == []: continue\n",
    "        elif min(d[k]) < 3: return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0, [n])\n",
    "\n",
    "        return all([len(v) >= 3 for v in res])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        d = Counter()\n",
    "        s = []\n",
    "        for i in nums:\n",
    "            if i not in d:\n",
    "                s.append(i)\n",
    "            d[i] += 1\n",
    "        dp = [0,0,0]\n",
    "        bfnum = nums[0]-1\n",
    "        for i in s:\n",
    "            if i != bfnum + 1:\n",
    "                if dp[0] + dp[1] != 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    dp = [d[i],0,0]\n",
    "            else:\n",
    "                if d[i] < dp[0] + dp[1]:\n",
    "                    return False\n",
    "                else:\n",
    "                    dp = [max(0, d[i] - dp[0] - dp[1] - dp[2]),dp[0], dp[1] + min(d[i] - dp[0] -dp[1], dp[2])]\n",
    "            bfnum = i\n",
    "\n",
    "        return dp[0] + dp[1] == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        rec = defaultdict(list)\n",
    "        for num in nums:\n",
    "            if len(rec[num-1])>0:\n",
    "                min_len = heapq.heappop(rec[num-1])\n",
    "                heapq.heappush(rec[num], min_len+1)\n",
    "            else:\n",
    "                heapq.heappush(rec[num], 1)\n",
    "        for k,v in rec.items():\n",
    "            for length in v:\n",
    "                if length<3:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        need = {}\n",
    "        feq = {}\n",
    "        for k in nums:\n",
    "            feq[k] = feq.get(k,0) + 1\n",
    "        \n",
    "        for k in nums:\n",
    "            if feq[k] == 0: continue\n",
    "\n",
    "            if k in need and need[k] > 0:\n",
    "                feq[k] -= 1\n",
    "                need[k] -= 1\n",
    "                need[k+1] = need.get(k+1, 0) + 1\n",
    "            \n",
    "            elif feq.get(k + 1, 0) > 0 and feq.get(k + 2, 0) > 0:\n",
    "                feq[k] -= 1\n",
    "                feq[k+1] -= 1\n",
    "                feq[k+2] -= 1\n",
    "                need[k+3] = need.get(k+3, 0) + 1\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        count = {}\n",
    "        need = {}\n",
    "        n = len(nums)\n",
    "        for num in nums:\n",
    "            count[num] = count.get(num, 0) + 1\n",
    "            need[num] = 0\n",
    "        \n",
    "        for num in nums:\n",
    "            if count[num] == 0:\n",
    "                continue\n",
    "            if need[num] > 0:\n",
    "                need[num+1] = need.get(num + 1, 0) + 1\n",
    "                count[num] -= 1\n",
    "                need[num] -= 1\n",
    "            elif count.get(num+1, 0) > 0 and count.get(num+2, 0) > 0:\n",
    "                count[num] -= 1\n",
    "                count[num+1] -= 1\n",
    "                count[num+2] -= 1\n",
    "                need[num+3] = need.get(num + 3, 0) + 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        d = defaultdict(list)\n",
    "\n",
    "        for num in nums:\n",
    "            if len(d[num - 1]) > 0:\n",
    "                l = heappop(d[num - 1])\n",
    "                heappush(d[num], l + 1)\n",
    "            else:\n",
    "                heappush(d[num], 1)\n",
    "        return min(reduce(lambda x, y: x + y, d.values())) > 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0, [n])\n",
    "        return all([len(v) >= 3 for v in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                if n+1 in nums and n+2 in nums:\n",
    "                    res.insert(0, [n])\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        return all([len(v) >= 3 for v in res])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        if len(nums) < 3:\n",
    "            return False\n",
    "        temp = []\n",
    "        temp.append(0)\n",
    "        len_tmep = 1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] != nums[i-1]:\n",
    "                temp.append(len_tmep)\n",
    "                for k in range(nums[i] - nums[i-1]-1):\n",
    "                    temp.append(0)\n",
    "                len_tmep = 1\n",
    "            else:\n",
    "                len_tmep += 1\n",
    "            if i == len(nums)-1:\n",
    "                temp.append(len_tmep)\n",
    "        flag = 0\n",
    "        while len(temp) > 3:\n",
    "            i = 1\n",
    "            while temp[i] == 0:\n",
    "                temp.pop(i)\n",
    "            print(temp)\n",
    "            while temp[i] > temp[i-1]:\n",
    "                temp[i] -= 1\n",
    "                flag += 1\n",
    "                if temp[i] == 0:\n",
    "                    temp.pop(i)\n",
    "                    i -= 1\n",
    "                i += 1\n",
    "                if i  == len(temp):\n",
    "                    break\n",
    "            if flag <3:\n",
    "                return False\n",
    "            else:\n",
    "                flag = 0\n",
    "        if len(temp)  == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1]+1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0,[n])\n",
    "        print(res)\n",
    "        return all([len(v)>=3 for v in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        min_heap = {}  # type: Dict[int, List]\n",
    "        for num in nums:\n",
    "            if num - 1 in min_heap:\n",
    "                if min_heap[num-1] == []:\n",
    "                    heapq.heappush(min_heap[num], 1)\n",
    "                else :\n",
    "                    if num not in min_heap:\n",
    "                        min_heap[num] = []\n",
    "                    heapq.heappush(min_heap[num], heapq.heappop(min_heap[num - 1]) + 1)\n",
    "            else:\n",
    "                if num not in min_heap:\n",
    "                    min_heap[num] = []\n",
    "                heapq.heappush(min_heap[num], 1)\n",
    "        for item in min_heap:\n",
    "            if len(min_heap[item]) != 0 and heapq.heappop(min_heap[item]) < 3:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        # 贪心\n",
    "        # 先每个串自成一行，如果后面能加在前面 优先加前面，加完在自成一行\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else: # 如果for循环正常结束，else中语句执行。如果是break的，则不执行。\n",
    "                # 如果在res中没有找到可以接的  就另起一个，如果找到就不起了\n",
    "                res.insert(0,[n]) \n",
    "        return all([len(v)>=3 for v in res])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        # 贪心\n",
    "        # 先每个串自成一行，如果后面能加在前面 优先加前面，加完在自成一行\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else: # 如果for循环正常结束，else中语句执行。如果是break的，则不执行。\n",
    "                # 如果在res中没有找到可以接的  就另起一个，如果找到就不起了\n",
    "                res.insert(0,[n]) \n",
    "        return all([len(v)>=3 for v in res])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        holder = []\n",
    "        for i in nums:\n",
    "            found = False\n",
    "            for j in holder:\n",
    "                if i == j[-1]+1:\n",
    "                    j.append(i)\n",
    "                    found = True\n",
    "                    break\n",
    "            if not found:\n",
    "                holder.insert(0, [i])\n",
    "        for i in holder:\n",
    "            if len(i) < 3:\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0, [n])\n",
    "\n",
    "        return all([len(v) >= 3 for v in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(res)):\n",
    "                if res[j][-1]+1 == nums[i]:\n",
    "                    res[j].append(nums[i])\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0, [nums[i]])\n",
    "        if any(len(k)<3 for k in res) :\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        freq = {}\n",
    "        need = {}\n",
    "        for i in nums:\n",
    "            if i not in freq:\n",
    "                freq[i] = 1\n",
    "            else:\n",
    "                freq[i] += 1\n",
    "        \n",
    "        for v in nums:\n",
    "            if freq[v] == 0:\n",
    "                continue\n",
    "            if v in need and need[v] > 0:\n",
    "                freq[v] -= 1\n",
    "                need[v] -= 1\n",
    "                if v+1 not in need:\n",
    "                    need[v+1] = 1\n",
    "                else:\n",
    "                    need[v+1] += 1\n",
    "            elif freq[v] > 0 and (v+1 in freq and freq[v+1] > 0) and(v+2 in freq and freq[v+2] > 0):\n",
    "                freq[v] -= 1\n",
    "                freq[v+1] -= 1\n",
    "                freq[v+2] -= 1\n",
    "                if v+3 not in need:\n",
    "                    need[v+3] = 1\n",
    "                else:\n",
    "                    need[v+3] += 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        pre = nums[0]\n",
    "        lists = []\n",
    "        current = 0\n",
    "        for num in nums:\n",
    "            if num != pre:\n",
    "                if num - pre > 1:\n",
    "                    lists.append([num])\n",
    "                    current = len(lists) - 1\n",
    "                else:\n",
    "                    current = len(lists) - 1\n",
    "                    lists[current].append(num)\n",
    "            elif current == 0 or num == lists[current-1][-1]:\n",
    "                lists.append([num])\n",
    "                current = len(lists) - 1\n",
    "            else:\n",
    "                current -= 1\n",
    "                if num - lists[current][-1] > 1:\n",
    "                    lists.append([num])\n",
    "                    current = len(lists) - 1\n",
    "                else:\n",
    "                    lists[current].append(num)\n",
    "            pre = num\n",
    "        return min([len(l) for l in lists]) >= 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0, [n])\n",
    "        return all([len(v) >= 3 for v in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0, [n])\n",
    "        # return res\n",
    "        return all([len(v) >= 3 for v in res])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res=[]\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n==v[-1]+1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0,[n])\n",
    "        return all([len(u)>=3 for u in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        heaps = defaultdict(list)\n",
    "\n",
    "        for num in nums:\n",
    "            if heaps[num - 1]:  # 延长最短的以 num - 1 结尾的子序列\n",
    "                length, _ = heapq.heappop(heaps[num - 1])\n",
    "                heapq.heappush(heaps[num], (length + 1, num))\n",
    "            else:  # 开始一个新的子序列\n",
    "                heapq.heappush(heaps[num], (1, num))\n",
    "\n",
    "        # 检查所有子序列的长度是否至少为 3\n",
    "        return all(len(subseq) == 0 or subseq[0][0] >= 3 for subseq in heaps.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        countMap = collections.Counter(nums)\n",
    "        endMap = collections.Counter()\n",
    "        print(countMap,endMap)\n",
    "        for x in nums:\n",
    "            if (count := countMap[x]) > 0:\n",
    "                if (prevEndCount := endMap.get(x - 1, 0)) > 0:\n",
    "                    print(prevEndCount)\n",
    "                    countMap[x] -= 1\n",
    "                    endMap[x - 1] = prevEndCount - 1\n",
    "                    endMap[x] += 1\n",
    "                    print(endMap)\n",
    "                else:\n",
    "                    if (count1 := countMap.get(x + 1, 0)) > 0 and (count2 := countMap.get(x + 2, 0)) > 0:\n",
    "                        countMap[x] -= 1\n",
    "                        countMap[x + 1] -= 1\n",
    "                        countMap[x + 2] -= 1\n",
    "                        endMap[x + 2] += 1\n",
    "                        print(endMap)\n",
    "                    else:\n",
    "                        return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        dct = {}\n",
    "        for i in nums:\n",
    "            if i-1 not in dct:\n",
    "                if i in dct:\n",
    "                    heappush(dct[i], 1)\n",
    "                else:\n",
    "                    dct[i] = [1]\n",
    "                    heapify(dct[i])\n",
    "            else:\n",
    "                if len(dct[i-1]) == 1:\n",
    "                    p = dct[i-1][0]\n",
    "                    del dct[i-1]\n",
    "                else:\n",
    "                    p = heappop(dct[i-1])\n",
    "                if i in dct:\n",
    "                    heappush(dct[i], p+1)\n",
    "                else:\n",
    "                    dct[i] = [p+1]\n",
    "                    heapify(dct[i])\n",
    "        return all(i >= 3 for i in sum(dct.values(), []))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            for v in res:\n",
    "                if n == v[-1] + 1:\n",
    "                    v.append(n)\n",
    "                    break\n",
    "            else:\n",
    "                res.insert(0, [n])\n",
    "\n",
    "        return all([len(v) >= 3 for v in res])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPossible(self, nums: List[int]) -> bool:\n",
    "        seq_map = {}\n",
    "        for num in nums:\n",
    "            if (num - 1) not in seq_map or len(seq_map[num - 1]) == 0:\n",
    "                new_seq = (num, 1)\n",
    "            else:\n",
    "                pre = heapq.heappop(seq_map[num - 1])\n",
    "                new_seq = (num, pre[1] + 1)\n",
    "            if num not in seq_map:\n",
    "                seq_map[num] = []\n",
    "            heapq.heappush(seq_map[num], new_seq)\n",
    "        for num, heap in seq_map.items():\n",
    "            for i in range(len(heap)):\n",
    "                if heap[i][1] < 3:\n",
    "                    return False\n",
    "        return True\n",
    "            \n",
    "            \n",
    "             \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
